#pragma once
#include <bits/stdc++.h>
using namespace std;
class TreeNode
{
public:
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

TreeNode* createtree(vector<int>& array)
{
    if (array.empty() || array[0] == NULL)
    {
        return nullptr;
    }

    int index = 0;
    int length = array.size();

    TreeNode* root = new TreeNode(array[0]);
    std::deque<TreeNode*> nodeQueue;
    nodeQueue.push_back(root);
    TreeNode* currNode;
    while (index < length)
    {
        index++;
        if (index >= length)
        {
            return root;
        }
        currNode = nodeQueue.front();
        nodeQueue.pop_front();
        int leftChild = array[index];
        if (leftChild != NULL)
        {
            currNode->left = new TreeNode(leftChild);
            nodeQueue.push_back(currNode->left);
        }
        index++;
        if (index >= length)
        {
            return root;
        }
        int rightChild = array[index];
        if (rightChild != NULL)
        {
            currNode->right = new TreeNode(rightChild);
            nodeQueue.push_back(currNode->right);
        }
    }
    return root;
}


struct ListNode
{
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};

ListNode* createlist(vector<int> nums)
{
    ListNode* newhead = new ListNode();
    ListNode* tail = newhead;
    for (auto e : nums)
    {
        tail->next = new ListNode(e);
        tail = tail->next;
    }
    return newhead->next;
}

void printlist(ListNode* head)
{
    ListNode* cur = head;
    while (cur)
    {
        cout << cur->val << "->";
        cur = cur->next;
    }
    cout << "null" << endl;
}

void printtree(TreeNode* root)
{
    if (root == nullptr)
        return;
    cout << root->val << " ";
    printtree(root->left);
    printtree(root->right);
}